// 队列 + 宽搜
// N叉树/二叉树 的层序遍历：借助一个队列实现

// 例题 2：
// 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
//
//        示例 1：
//
//        输入：root = [3,9,20,null,null,15,7]
//        输出：[[3],[20,9],[15,7]]
//        示例 2：
//
//        输入：root = [1]
//        输出：[[1]]
//        示例 3：
//
//        输入：root = []
//        输出：[]
//
//
//        提示：
//
//        树中节点数目在范围 [0, 2000] 内
//        -100 <= Node.val <= 100

// 解题思路：
// 借助一个队列，运用队列先进先出的特性，依次让每个节点入队
// 统计每一层的节点个数，实现分层，最终实现层序遍历
// 这个题目要求 锯齿形 遍历，要注意将偶数层的节点逆序（双指针）

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ZigzagLevelOrder {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int n = 0;
        while(!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            if(n % 2 == 1) reverse(tmp);
            ret.add(tmp);
            n++;
        }
        return ret;
    }
    public void reverse(List<Integer> nums){
        int left = 0; int right = nums.size() - 1;
        while(left < right){
            int tmp = nums.get(left);
            nums.set(left, nums.get(right));
            nums.set(right, tmp);
            left++;
            right--;
        }
    }
}
